Maximum average subtree [DFS]¶
Time: O(N); Space: O(H); easy
Given the root of a binary tree, find the maximum average value of any subtree of that tree.
(A subtree of a tree is any node of that tree plus all its descendants. The average value of a tree is the sum of its values, divided by the number of nodes.)
Example 1:
5
/ \
6 1
Input: root = {TreeNode} [5,6,1]
Output: 6.00000
Explanation:
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.
Constraints:
The number of nodes in the tree is between 1 and 5000.
Each node will have a value between 0 and 100000.
Answers will be accepted as correct if they are within 10^-5 of the correct answer.
[1]:
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
1. Depth First Search¶
[2]:
class Solution1(object):
"""
Time: O(N)
Space: O(H)
"""
def maximumAverageSubtree(self, root):
"""
:type root: TreeNode
:rtype: float
"""
def maximumAverageSubtreeHelper(root, result):
if not root:
return [0.0, 0]
s1, n1 = maximumAverageSubtreeHelper(root.left, result)
s2, n2 = maximumAverageSubtreeHelper(root.right, result)
s = s1 + s2 + root.val
n = n1 + n2 + 1
result[0] = max(result[0], s / n)
return [s, n]
result = [0]
maximumAverageSubtreeHelper(root, result)
return result[0]
[3]:
s = Solution1()
root = TreeNode(5)
root.left = TreeNode(6)
root.right = TreeNode(1)
assert s.maximumAverageSubtree(root) == 6.00000
2. Depth First Search¶
[4]:
class Solution2(object):
def maximumAverageSubtree(self, root):
"""
:type root: TreeNode
:rtype: float
"""
ans = [0]
def helper(node):
if not node:
return 0, 0
left_sum, left_count = helper(node.left)
right_sum, right_count = helper(node.right)
ans[0] = max(ans[0], (left_sum + right_sum + node.val) / (left_count + right_count + 1))
return left_sum + right_sum + node.val, left_count + right_count + 1
helper(root)
return ans[0]
[5]:
s = Solution2()
root = TreeNode(5)
root.left = TreeNode(6)
root.right = TreeNode(1)
assert s.maximumAverageSubtree(root) == 6.00000